package LeetCode;

public class No33 {
    public static void main(String[] args) {
        int[] arr ={4,5,6,7,0,1,2};
        System.out.println(search1(arr, 0));
    }

    public static int search1(int[]nums,int target){
        int index = findMin(nums);
        if(target==nums[index]) return index;
        if(index==0){
            return getvalue(nums,0,nums.length-1,target);
        }else if(index==nums.length-1){
            return getvalue(nums,0,nums.length-2,target);
        }else {
            if (target > nums[index - 1]) return -1;
            else if (target < nums[index]) return -1;
            else if (target >= nums[0]) return getvalue(nums, 0, index - 1, target);
            else return getvalue(nums, index, nums.length - 1, target);
        }
    }

    public static int getvalue(int[]nums,int left,int right,int target){
        while(left<=right){
            int mid = (left +right)/2;
            if(nums[mid]== target) return mid;
            if(nums[mid]>target) right=mid-1;
            else left=mid+1;
        }
        return left==right?left:-1;
    }

    public static int findMin(int[] nums) {
        int n = nums.length-1;
        int left = 0,right=n;
        while(left<right){
            int mid =(left+right)/2;
            if(nums[mid]>=nums[n]){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return right;
    }

    public static int search(int[] nums, int target) {
        if(nums.length==0) return -1;
        if(nums.length==1) return nums[0]==target?0:-1;
        int left=0,right =nums.length-1;
        while(left<=right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && nums[nums.length - 1] >= target) left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }

}
